path counting.tex (1553B)
1 \begin{algorithmic} 2 \Function{Path counting}{} 3 \FunctionInputs{} \(G=(\entitySet, \arcSet, \gfendpoints, \gfrelation, \gfsentence)\) relation multigraph 4 \FunctionInputs*{} \(k\) paths length 5 \FunctionOutput{} \(C\) relation paths counter 6 \State 7 \LComment{Initialization} 8 \State \(C \gets \text{new counter}\ \relationSet^k \to \symbb{R}\ \text{initialized at 0}\) 9 \LComment{Main Loop} 10 \Loop 11 \LComment{Initialize the importance weight with \(\symcal{W}^k\)} 12 \State \(w \gets \left(\symbf{1}\transpose \mtrx{M}^k \symbf{1}\right)^{-1}\) 13 \Comment{\(\mtrx{M}\) is the adjacency matrix} 14 \State Initialize empty walk \(\vctr{a}=()\) 15 \State Sample \(v\sim \uniformDistribution(\entitySet)\) 16 \State \(w \gets n \times w\) 17 \Comment{Update \(w\) following the sampling of \(v\)} 18 \For{\(i=1,\dotsc,k\)} 19 \State Sample \(x\sim\uniformDistribution(\gfincidents(v))\) 20 \State \(w \gets w \times \gfdegree(v)\) 21 \Comment{Accumulate \(1\divslash\symcal{F}^k\)} 22 \If{\(\gfsource(x) = v\)} 23 \Comment{Continue with \(\gfendpoints(x)\setminus\{v\}\)} 24 \State Append \(x\) to \(\vctr{a}\) 25 \State \(v\gets \gftarget(x)\) 26 \Else 27 \State Append \(\breve{x}\) to \(\vctr{a}\) 28 \State \(v\gets \gfsource(x)\) 29 \EndIf 30 \EndFor 31 \If{\(\vctr{a}\) is a path} 32 \State \(\vctr{r} \gets (\gfrelation(a_i))_{1\leq i\leq k}\) 33 \Comment{Take the relations of \(\vctr{a}\)} 34 \State \(C[\vctr{r}] \gets C[\vctr{r}] + w\) 35 \EndIf 36 \EndLoop 37 \State \Output \(C\) 38 \EndFunction 39 \end{algorithmic}